/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 直接插入排序是指将一个个待排序的元素插入到前面已经排好序的有序序列中去，直到插完所有元素为止，主要步骤如下
 *
 * <p>1）先假设第一个元素已经排好序
 * <p>2）然后依次取出还需要进行排序的下一个元素，也就是排序完成的元素后面的下一个元素，取出下一个元素，设为待插入元素
 * 在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。
 * <p>3）重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素
 * <p>4）重复步骤2、步骤3，完成排序
 * <p>
 * 直接插入排序最好情况下的时间复杂度为 O(n)。最坏情况下的时间复杂度为 O(n²)。
 * <a href="https://www.dotcpp.com/course/898">课程地址</a>
 *
 * @author lizhixing
 */
public class InsertSort {

  public static void main(String[] args) {
    int[] data = { 43, 55, 70, 30, 5 };
    print(data);
    insertSort(data);
    print(data);
  }

  /**
   * 直接插入排序
   *
   * @param data
   *     待排序数组
   */
  public static void insertSort(int[] data) {

    for (int i = 1; i < data.length; i++) { //从第二个元素开始比较
      int temp = data[i]; //记录当前元素
      for (int j = i - 1; j >= 0; j--) { //从最后一个元素开始比较
        if (data[j] > temp) { //如果比当前元素大
          data[j + 1] = data[j]; //从该处往后所有元素向后移动一位
          data[j] = temp; //将当前元素插入到arr[j]中
        }
      }
    }
  }

  public static void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }

}
